#include <iostream>
using namespace std;
/*
设计一个表示链表的类型 LinkList，让它支持以下操作：

Group 1
LinkList l; 创建一个空链表

Group 2
l.print(); 打印链表里的所有元素

Group 3
l.addAtIndex(1, 13);
...
*/
class Node {
public:
  int value;  // 节点里的值
  Node *next; // 节点的下一个位置

  Node(int v, Node *p) {
    value = v;
    next = p;
  }
};

class LinkList {
public:
  Node *head;
  int size; // 链表中元素的个数

  LinkList() {
    head = nullptr;
    size = 0;
  }

  void print() {
    Node *current = head;
    
    while (head != nullptr) {
      cout << current->value << " ";
      current = current->next;
    }
    cout << endl;
  }

  // 0     1     2     3     4     5
  // 11 -> 12 -> 20 -> 13 -> 14 -> 15 -> nullptr
  // addAtIndex(2, 20);
  // 
  void addAtIndex(int pos, int v) {
    // 1. 确保 pos 的位置是合法的
    if (pos < 0 || pos > size) {
      cout << "Invalid position: " << pos << endl;
      return;
    }

    // 2. 用 v 创建一个 Node
    Node *toAdd = new Node(v, nullptr);

    // 3. 把这个节点添加到链表正确的位置
    // ...
    ++size;
    if (head == nullptr) {
      head = toAdd;
    }
    else {
      // 找到 pos 的前一个位置
      Node *tmp = head;
      int i = 0;

      while (i < pos - 1) {
        tmp = tmp->next;
        ++i;
      }

      // tmp 指向了要插入位置的前一个位置
      toAdd->next = tmp->next;
      tmp->next = toAdd;
    }
  }

  void addAtHead(int v) {
    addAtIndex(v, 0);
  }

  void addAtTail(int v) {
    addAtIndex(size, v);
  }

  // 判断以 head 为首的链表是否存在循环
  // bool hasCycle() {

  // }

  // 返回指向 pos 位置的节点指针
  /*
  Node *getNode(int pos) {
    // 1. 确保 pos 是合法的
    if (pos < 0 || pos >= size) {
      return nullptr;
    }

    // 2. 从 head 开始移动到 pos 位置
    // ...
  }
  */

  // 删除位置 pos 处的节点
  void deleteAtIndex(int pos) {

  }


  void reverse() {
    // 
  }

  // 从链表中的 pNode 位置开始，把之后的所有节点逆序
  // 返回逆序之后的新表头
  Node *reverse(Node *pNode) {
    if (pNode == nullptr) { return nullptr; }

    Node *currH = pNode;
    while (pNode->next != nullptr) {
      Node *q = pNode->next;
      pNode->next = q->next;
      q->next = currH;
      currH = q;
    }

    return currH;
  }

  // 0                   4
  // h
  // 1 -> 3 -> 2 -> 3 -> 1
  //           ^mid
  //           1 -> 3 -> 2 -> nullptr

  // 0              3
  // h
  // 1 -> 3 -> 3 -> 1
  //      ^mid
  //      1 -> 3 -> 3 -> nullptr
  bool isPalindrome() {
    
  }
};